package com.s6.other;

import com.s6.sort1.ArrayUtils;

/**
 * 求无序数组中的第 K 大元素(下标为 k - 1)
 */
public class KthSmallest {

	public static void main(String[] args) {
		int[] arr = { 4, 2, 5, 12, 3 };
		ArrayUtils.print(arr);

		System.out.println(kthSmallest(arr, 1));
		System.out.println(kthSmallest2(arr, 2));
		System.out.println(kthSmallest(arr, 3));
		System.out.println(kthSmallest2(arr, 4));
	}

	// 非递归实现
	public static int kthSmallest(int[] arr, int k) {
		if (arr == null || arr.length < k) {
			return -1;
		}
		int pivot = partition(arr, 0, arr.length - 1);
		while (k != pivot + 1) {
			if (k > pivot + 1) {
				pivot = partition(arr, pivot + 1, arr.length - 1);
			} else {
				pivot = partition(arr, 0, pivot - 1);
			}
		}
		return arr[pivot];
	}

	private static int partition(int[] array, int start, int end) {
		int pivotValue = array[end];
		int i = start;
		for (int j = start; j < end; j++) {
			if (array[j] < pivotValue) {
				ArrayUtils.swap(array, i, j);
				i++;
			}
		}
		ArrayUtils.swap(array, i, end);
		return i;
	}

	// 递归实现 求无序数组中[0, length -1]中的第 K 大元素(下标为 k - 1)
	public static int kthSmallest2(int[] arr, int k) {
		if (arr == null || arr.length < k) {
			return -1;
		}
		return kthSmallest2(arr, 0, arr.length - 1, k);
	}

	private static int kthSmallest2(int[] arr, int start, int end, int k) {
		int pivot = partition(arr, start, end);
		if (k == pivot + 1) {
			return arr[pivot];
		} else if (k > pivot + 1) {
			return kthSmallest2(arr, pivot + 1, end, k);
		} else {
			return kthSmallest2(arr, start, pivot - 1, k);
		}
	}
}
